package Library

import (
	"errors"
	"fmt"
	"math/rand"
	"sync"
)

var MIN int = -1 // Min key

type SkipList struct {
	Head  *Node        // Point to the skiplist header
	Depth int          // Current SkipList depth, start from 0
	mutex sync.RWMutex // Lock
}

type Node struct {
	prev, next, down *Node
	Key              int // Insert Key
	Value            interface{}
}

func getDepth(max int) (depth int) {
	for i := 0; i <= max; i++ {
		if rand.Intn(2) == 0 {
			depth = i
			break
		}
	}

	return
}

func insert(head *Node, key int, value interface{}) (node *Node) {
	if head == nil {
		return
	}

	p := head
	for p.Key < key && p.next != nil && p.next.Key <= key {
		p = p.next
	}

	node = &Node{Key: key, Value: value, next: p.next, prev: p}
	node.down = insert(p.down, key, value)
	if p.next != nil {
		p.next.prev = node
	}
	p.next = node

	return
}

func (sl *SkipList) Init() {
	sl.Depth = 0
	sl.Head = &Node{Key: MIN}
}

func (sl *SkipList) Insert(key int, value interface{}) (err error) {
	depth := getDepth(sl.Depth + 1)

	sl.mutex.Lock()
	defer sl.mutex.Unlock()

	if node, _ := search(sl.Head, key); node != nil {
		err = errors.New("Duplicated Key")
		return
	}

	if depth > sl.Depth {
		head := &Node{Key: MIN, next: nil, down: sl.Head}
		sl.Head = head
		sl.Depth = depth
	}

	insert(sl.Head, key, value)

	return
}

func search(head *Node, key int) (node *Node, err error) {
	p := head

	if p == nil {
		return
	}

	for p.Key < key && p.next != nil && p.next.Key <= key {
		p = p.next
	}

	if p.Key == key {
		node = p
		return
	}

	node, err = search(p.down, key)
	return
}

func (sl *SkipList) Search(key int) (value interface{}, err error) {
	elm := sl.Head

	sl.mutex.RLock()
	defer sl.mutex.RUnlock()

	node, _ := search(elm, key)
	if node != nil {
		value = node.Value
	}
	return
}

func (sl *SkipList) Delete(key int) (err error) {
	p := sl.Head

	sl.mutex.Lock()
	defer sl.mutex.Unlock()

	for {
		if p == nil {
			break
		}

		for p.Key < key && p.next != nil && p.next.Key <= key {
			p = p.next
		}

		if p.Key != key {
			p = p.down
		} else {
			break
		}
	}

	for p != nil {
		if p.next != nil {
			p.next.prev = p.prev
		}
		p.prev.next = p.next
		p = p.down
	}
	return
}

func (sl *SkipList) Show() {
	node := sl.Head
	for node != nil {
		p := node
		for p != nil {
			fmt.Print(p.Key, ":", p.Value, " ==> ")
			p = p.next
		}
		fmt.Println()
		node = node.down
	}
}
